using System;
using System.Collections.Generic;

namespace LannyPractiseCode.Shu
{
    public class HuffmanTree
    {
        public static void PreOrder(HuffmanNode root)
        {
            if(root !=null)
                root.PreOrder();
            else
                System.Console.WriteLine("空树，不能遍历！！");
        }

        /// <summary>
        /// 返回根节点
        /// </summary>
        /// <param name="arr"></param>
        /// <returns></returns>
        public static HuffmanNode CreateHuffumanTree(int[] arr)
        {
            //第一步为了操作方便
            // 1.遍历arr数组
            // 2.将arr的每个元素构成成一个HuffmanNode
            // 3.将HuffmanNode 放入到ArrayList中
            List<HuffmanNode> nodes=new List<HuffmanNode>();
            for (int i = 0; i < arr.Length; i++)
            {
                nodes.Add(new HuffmanNode(arr[i]));
            }

            //处理过程是一个循环过程。。
            while(nodes.Count>1)
            {
                //List.Sort(nodes);
                nodes.Sort();
                System.Console.WriteLine("node="+nodes);

                //取出根节点权值最小的两颗二叉 树
                //(1)取出权值最小的结点(二叉树)
                HuffmanNode leftNode=nodes[0];
                //(2)取出权值第二小的结点
                HuffmanNode rightNode=nodes[1];
                //(3)构建一颗新的二叉树
                HuffmanNode parent=new HuffmanNode(leftNode.Value+rightNode.Value);
                parent.Left=leftNode;
                parent.Right=rightNode;

                //(4)从ArrayList删除处理过的二叉树
                nodes.Remove(leftNode);
                nodes.Remove(rightNode);

                //(5)将parent加入
                nodes.Add(parent);
            }

            return nodes[0];
        }
    }
}